package uk.ac.strath.cis.metric_spaces.indices;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import uk.ac.strath.cis.metric_spaces.framework.AbstractMetricIndex;
import uk.ac.strath.cis.metric_spaces.framework.Distance;
import uk.ac.strath.cis.metric_spaces.framework.MetricIndex;

/**
 * @author Robert
 *
 * @param <E>
 */
public class BisectorTree<E> extends AbstractMetricIndex<E> {

    private class Centre {
        E element;
        double coveringRadius;

        @Override
        public String toString() {
            return element + ":" + coveringRadius;
        }
    }

    private Centre c1;
    private Centre c2;
    private BisectorTree<E> left;
    private BisectorTree<E> right;

    /**
     * @param metric
     */
    public BisectorTree(Distance<E> metric) {
        super(metric);
    }

    /**
     * @param copy
     */
    public BisectorTree(BisectorTree<E> copy) {
        super(copy);
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.AbstractMetricIndex#insert(java.util.Set)
     */
    public void insert(Set<E> elements) {
        super.insert(elements);
        insert(new ArrayList<E>(elements));
    }

    /**
     * @param elements
     */
    public void insert(List<E> elements) {
        c1 = initCentre(elements, 0);
        c2 = initCentre(elements, 1);

        addSubtrees(elements);
    }

    /**
     * returns an initialized centre object from ith element of the list
     * 
     * @param elements
     * @param i
     * @return
     */
    private Centre initCentre(List<E> elements, int i) {
        Centre c = null;
        if (elements.size() > i) {
            c = new Centre();
            c.element = elements.get(i);
            c.coveringRadius = 0.0;
        }
        return c;
    }

    /**
     * precondition: elements.size() > 2 implies c1 != null && c2 != null.
     * 
     * Subtrees can only be made if both c1 and c2 have been initialized
     * 
     * @param elements
     */
    private void addSubtrees(List<E> elements) {
        if (elements.size() > 2) {
            List<E> subList = elements.subList(2, elements.size());
            addSubtrees(c1, c2, subList);
        }
    }

    private void addSubtrees(Centre c1, Centre c2, List<E> subList) {
        List<E> leftSubtree = new ArrayList<E>();
        List<E> rightSubtree = new ArrayList<E>();
        for (E e : subList) {
            double d1 = distance(c1.element, e);
            double d2 = distance(c2.element, e);
            if (d1 < d2) {
                c1.coveringRadius = d1 > c1.coveringRadius ? d1
                        : c1.coveringRadius;
                leftSubtree.add(e);
            } else {
                c2.coveringRadius = d2 > c2.coveringRadius ? d2
                        : c2.coveringRadius;
                rightSubtree.add(e);
            }
        }

        if (leftSubtree.size() > 0) {
            left = new BisectorTree<E>(this);
            left.insert(leftSubtree);
        }

        if (rightSubtree.size() > 0) {
            right = new BisectorTree<E>(this);
            right.insert(rightSubtree);
        }
    }

    /* (non-Javadoc)
     * @see uk.ac.strath.cis.rmoss.metric_spaces.framework.MetricIndex#rangeQuery(java.lang.Object, double)
     */
    public Set<E> rangeQuery(E element, double radius) {
        Set<E> returnSet = new HashSet<E>();
        rangeQuery(returnSet, element, radius);
        return returnSet;
    }

    private void rangeQuery(Set<E> returnSet, E element, double radius) {
        rangeQuery(element, radius, returnSet, c1, left);
        rangeQuery(element, radius, returnSet, c2, right);
    }

    private void rangeQuery(E element, double radius, Set<E> returnSet,
            Centre c, BisectorTree<E> subtree) {
        if (c != null) {
            double d = distance(element, c.element);
            if (d <= radius) {
                returnSet.add(c.element);
            }
            if ((d - radius <= c.coveringRadius) && (subtree != null)) {
                subtree.rangeQuery(returnSet, element, radius);
            }
        }
    }

    private String toString(StringBuilder sb, BisectorTree<E> node) {
        if (node == null) {
            return sb.append("{}").toString();
        }
        sb.append("{" + node.c1 + ", " + node.c2 + "}");
        if ((node.left != null) || (node.right != null)) {
            sb.append("(");
            toString(sb, node.left);
            sb.append(", ");
            toString(sb, node.right);
            sb.append(")");
        }
        return sb.toString();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        return this.toString(sb, this);
    }
    
    @Override
    public MetricIndex<E> clone() {
    	return new BisectorTree<E>(this);
    }

}
